# -*- coding: utf-8 -*-            
# @Time : 2022/10/22 13:52
# @Author  : lining
# @FileName: group__reverse_list1.py


class Node():
    """
    创建结点
    """
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

class LinkList():
    def __init__(self):
        # 头结点
        self.head = Node()
        self.length = 0

    def append_node(self, data):
        """
        单向链表追加节点
        :param data:
        :return:
        """
        temp = self.head
        new_node = Node(data)
        if temp.next is None:
            temp.next = new_node
        else:
            while temp.next is not None:
                temp = temp.next
            temp.next = new_node
        self.length = self.length + 1

    def print_list(self):
        """
        打印链表
        :return:
        """
        if self.head.next is None:
            print('空列表')
            return
        temp = self.head.next
        while temp:
            print(temp.data)
            temp = temp.next
        print('打印结束')

    # 反转链表
    def reverse_list(self, start, end):
        """
        start开始节点，end结束节点
        反转需要三个节点
        （1）开始节点，知道从哪个节点开始反转
        （2）结束节点：知道在哪个节点结束反转
        （3）当前要反转的节点的下一个节点，需要保存该节点，因为前一个节点反转后这个节点就会丢失
        反转流程
        （1）取到第一个节点
        （2）取到第二个节点
        （3）取到第三个节点，保存
        （4）把第二个节点指向第一个节点
        （5）去第二个节点为第一个节点
        （6）取第三个节点为第二个节点
        （7）一直到最后一个None
        """
        node_1 = start.next
        while node_1:
            node_2 = node_1.next
            node_1.next = start
            if node_1 is end:
                break
            start = node_1
            node_1 = node_2

    def group_list(self, k):
        """
        k个一组反转链表
        1-2-3-4-5三个一组 3-2-1-4-5
        （1）按照k进行分组，拿到k个一组的头节点和尾节点
        （2）[1]把这k个节点进行反转
             [2]如果剩余个数不足k个就不反转
        （3）把多个组之间进行连接--需要保存上一次的尾节点,从保护节点开始连接，如果最后一组正好分成k个要把最后一个节点指向None
        测试用例
        （1）正好分成n组
        （2）最后一组个数小于k
        """

        # 连接边的时候从last节点开始连接
        last = self.head
        # 第一个节点
        current = last.next
        i = 1
        start = None
        # 找个一组的k个
        while True:
            # 先按照k进行分组，保存头结点和为节点
            # 正好可以分成n组
            if current is None:
                last.next = None
                break
            # 保存开始节点
            if i == 1:
                start = current
            # 不能正好分成n组，直接连接第一个
            if current.next is None and i < k:
                last.next = start
                break
            # 取到k个进行反转
            elif i == k:
                end = current
                # 先保存当前的下一个节点
                end_next = end.next
                self.reverse_list(start, end)
                # 把两条边连接起来
                last.next = end
                last = start
                i = 1
                current = end_next
                continue
            current = current.next
            i = i + 1

a = LinkList()
a.append_node(1)
a.append_node(2)
a.append_node(3)
a.append_node(4)
a.append_node(5)
a.append_node(6)
a.group_list(4)
a.print_list()

